/********************
*dp[i][j]: s1[0..i]和s2[0..j]的最长公共子序列的长度
*sr[i][j]: s1[0..i]和s2[0..j]的最长公共子序列的最后一个元素的下标
*dp[i][j] = {
*   s1[i]==s2[j] ?1: 0,              i=0 || j=0   
*   dp[i-1][j-1]+1,                  s1[i]=s2[j]       
*   max(dp[i-1][j], dp[i][j-1]),     other
*}
*dp[i][]只依赖dp[i-1][]和自身, 因此可以降维, 先直接计算i=0的情况: predp[j]
*predp[j] = s1[0]==s2[j] ?1: 0
*dp[j] = {
*   s1[i]==s2[0] ?1: 0, j=0
*   predp[j-1]+1, s1[i]=s2[j]
    max(predp[j], dp[j-1]), other       
*}
*dp[j]只依赖predp[j-1]和predp[j], 因此可进一步优化, 先直接计算i=0的情况: dp[j]
*dp[j] = s1[0]==s2[j] ?1: 0
*令prei_prej = dp[0], 表示predp[j-1]
*dp[j] = { //i>0
*   tmp = dp[j];
*   dp[0] = s1[i]==s2[0] ?1: 0, j=0
    prei_prej+1, elif s1[i] = s2[j]
    max(dp[j], dp[j-1]), else 
*   prei_prej = tmp 
*}
*sr[i][j] = {
*   (i, j), s1[i]==s2[j]
*   sr[i-1][j], dp[i-1][j]>=dp[i][j-1]
*   sr[i][j-1], other
*}
*
********************/
#include <stdio.h>
#include <string>
#include <vector>
#include <array>

using namespace std;
typedef array<int, 2> IdxPair;
typedef  vector<vector<IdxPair>> IAVV;
typedef vector<int> IV;
class LCS {
private:
    string const &s1;
    string const &s2;
    IAVV sr;
public:
    LCS(string const &s1, string const &s2) : s1(s1), s2(s2) {}
    int lcs(void);
    void lcs_print(int x, int y);
};


int LCS::lcs(void) {
    int i, j;
    IV dp(s2.size()); 
    
    sr.resize(s1.size());
    for(i=0; i<s1.size(); i++) {
        sr[i].resize(s2.size());
    }
    for(j=0; j<s2.size(); j++) {  
        if(s1[1]==s2[j]) {
            dp[j] = 1;
            sr[0][j] = IdxPair{0, j};
        }else {
            dp[j] = 0;
            sr[0][j] = IdxPair{-1, -1};
        }
    }
    for(i=1; i<s1.size(); i++) {
        
        int prei_prej = dp[0]; //for dp[1..]
        // for dp[0]
        if(s1[i] == s2[0]) {
            dp[0] = 1;
            sr[i][0] = IdxPair{i, 0};
        }else {
            dp[0] = 0;
            sr[i][0] = IdxPair{-1, -1};
        }
        for(j=1; j<s2.size(); j++) {
            int tmp = dp[j]; //for prei_prej
            sr[i][j] = IdxPair{-1, -1};
            if(s1[i] == s2[j]) {
                dp[j] = prei_prej+1;
                sr[i][j] = IdxPair{i, j};
            }else if(dp[j] >= dp[j-1]) {
                //dp[j] = dp[j];
                sr[i][j] = sr[i-1][j];
            }else {
                dp[j] = dp[j-1];
                sr[i][j] = sr[i][j-1];               
            }
            prei_prej = tmp;
        }
    }
    return dp[j-1];
}

void LCS::lcs_print(int x, int y) {
    if(x<0 || y<0) return;
    lcs_print(sr[x][y][0]-1, sr[x][y][1]-1);
    printf("%c ", s1[sr[x][y][0]]);
}
int main(void)
{
    string str1("10010101");
    string str2("010110110");
    LCS lseq(str1, str2);
    printf("str1: %s\n", str1.c_str());
    printf("str1: %s\n", str2.c_str());
    printf("最长公共子序列:\n\t长度: %d\n\t", lseq.lcs());
    lseq.lcs_print(str1.size()-1, str2.size()-1);
    putchar('\n');
    return 0;
}
